package fun.codedesign.jdk.math.algorithm.sort;

/**
 * 快速排序 <br>
 * <pre>
 *     采用基数，递归排序，注意查找的顺序必须先从右到左
 * </pre>
 *
 * @author zengjian
 * @create 2018-06-25 19:51
 * @since 1.0.0
 */
public class QuickSorter implements Sorter {
    @Override
    public void sort(int[] arr) {
        // 快速排序范围，从0 到 arr.length-1
        quickSort(arr, 0, arr.length - 1);
    }

    private void quickSort(int[] arr, int lower, int higher) {
        if (lower < higher) {
            // 比较值
            int base = arr[lower];
            // 正向开始坐标
            int forward = lower;
            // 反向开始坐标
            int back = higher;

            // 只要两个还未相等即继续循环交换位置，最后将基准值放在中间
            while (forward < back) {
                // 从后往前，如果大于基准值，back-1
                while (arr[back] >= base && forward < back) {
                    back--;
                }

                // 从前往后，如果小于基准值，forward+1
                while (arr[forward] <= base && forward < back) {
                    forward++;
                }

                // 如果低位依然小于高位，高低位进行交换
                if (forward < back) {
                    SorterUtils.swap(arr, forward, back);
                }
            }
            // 将比较值放置到中间位置
            SorterUtils.swap(arr, lower, forward);
            // 递归左
            quickSort(arr, lower, forward - 1);
            // 递归右
            quickSort(arr, forward + 1, higher);
        }
    }
}
